package d_ch12.dijkstra;

import java.awt.List;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

import c_ch11.WeightedGraph;

public class Dijkstra_try {

    private WeightedGraph G;
    private int s; //source
    private int[] dis; //留下来的值 以及已经定的值;
    private boolean[] fixed; 	//辅助dis区分 已经定的值 和 留下来的值；

    public Dijkstra_try(WeightedGraph G, int s){

        this.G = G;

        G.validateVertex(s);
        this.s = s;

        dis = new int[G.V()];
        Arrays.fill(dis, Integer.MAX_VALUE);
        dis[s] = 0;
        
        fixed = new boolean[G.V()];

        /*
         *为什么这个逻辑是正确的？
         *
         * 我尝试了 不管怎么举反例调参数，结果总是正确的。。
         * 
         * 搞懂了 灵感来自百度百科：
         *
         * 现在的目的是找最短路径，要的是权值和最小，要的是 权值和最小！ 这样就行了啊，不管是怎么走的，只要是最短路径就好；
         * **DJ算法的正确打开方式 其实就是面向权值和的，算法是从路径*长度*出发，找全图最短的，再找次短的，并不关注你是哪个顶点，因为每条次短路径都涉及一个顶点，而这个顶点定下来后，下一轮找次短路径就不参与了，所以到达每个顶点的最短路径都能找到
         *	先找从s出发的，能找到全图最短路径s-V；排除顶点V（定下来了）（到该顶点的最短路径已经找到了）；
         *		然后找 从s出发的，次短长度的路径（在最短路径的长度上增加最少的距离）；这条路径要么是从s直接访问的长度（在上一轮留下的比最短长一些的路径），要么是基于上一轮的最短路径再走一步；
         *		所以 计算基于V处再走一步的距离，然后和上一轮留下的长度进行比较，择小进行更新；
         *		这时dis[]中最小的值就是次短路径长度；
         *	···
         * 
         * 每一轮寻找次短路径都会留下一批值，这批值不是当前轮次最短的，但有可能是下一轮最短的，因为下一轮的最短值要么是基于上一轮的最短值 +上一个最小权，要么是之前留下来的（留下来的值都是基于更早轮次的最短值 +上多走一步的权 得来的）（具体是之前的哪一轮次留下的是不确定也不需要关心的，因为某个dis更新的时候有可能真的更新了，也有可能不需要更新）
         * ，因此该思路要求权值必须为非负，如果不这样最短值是无法确定的，必须保证 对于最小权的路径 松弛操作一定是绕远的；
         * 
         * 所以算法思路就是：
         * 		求出每一轮的最短路径长度即可：
         * 				while(没有全部定下来时){ 基于上一轮定下的顶点 多走一步，然后更新dis[]，选择最小的那个值定下来；}
         *		
         *		变量dis的贴切语意应该是：留下来的值 和已经定的值，*我们只关注前者即可*，后者提醒我们要记得进行判断区分二者，处理过的就不要处理了；
         */
        
        //记录状态更新
        int cur = s;   //当前轮次选定的顶点（走0步的最短值就是dis[s]:0）；
        //每一个cur都要进行的操作
        while(true) {   
        	fixed[cur] = true;	//把cur定下来；定下来一个顶点也就代表当前轮次结束了；
        	
        	//下面 开始寻找下一个次短值（可能是在上一轮最短值的基础上多走一步的值，也有可能是上一轮留下来的 不多走一步的值）；
        	
        	// 更新留下来的值     在（淘汰下来的 不多走一步的值）和（在cur的基础上多走一步的值）之间取小；
        	for (int v : G.adj(cur)) {
        		if(!fixed[v] && dis[cur]+G.getWeight(cur, v) < dis[v]) //!visited[v] 区分出dis里留下来的值，已经定的值不能动；
        			dis[v] = dis[cur]+G.getWeight(cur, v);
        	}
        
        	// 更新后最小的值就是次短值  作为cur，定下来；
        	int min = Integer.MAX_VALUE; cur = -1;
        	for(int i = 0; i < G.V(); i++) {		 //这里决定了算法整体为O(V^2)
        		if(!fixed[i] && dis[i] < min) {
        			min = dis[i];
        			cur = i;
        		}
        	}
        	
        	if(cur == -1)  //结束判断；此时fixed不一定全为true，有可能图不连通，不可达的顶点dis永远保持无穷大；
        		break;
        	
//        	if(min == Integer.MAX_VALUE)  //结束判断，此时fixed不一定全为true，有可能图不连通，不可达的顶点dis永远保持无穷大；
//        		break;
        	
        																//BTW, if(fixed[i] = false)  一定要小心，有时候误写成 = 号 也不报错，只要等号右边是一个布尔值，这一句等价于先赋值再使用该值；这里写成等号就永远进不来了；
        }
    }

    public boolean isConnectedTo(int v){

        G.validateVertex(v);
        return fixed[v];
    }

    public int distTo(int v){

        G.validateVertex(v);
        return dis[v];
    }

    static public void main(String[] args){

        WeightedGraph g = new WeightedGraph("g_ch12.txt");
        Dijkstra_try dij = new Dijkstra_try(g, 0);
        for(int v = 0; v < g.V(); v ++)
            System.out.print(dij.distTo(v) + " ");
        System.out.println();
    }
}
